package protect.week02;

/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/9/8 20:41
 * @package protect.week02
 * @description 67. 二进制求和
 *
 * 给你两个二进制字符串，返回它们的和（用二进制表示）。
 *
 * 输入为 非空 字符串且只包含数字 1 和 0。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: a = "11", b = "1"
 * 输出: "100"
 * 示例 2:
 *
 * 输入: a = "1010", b = "1011"
 * 输出: "10101"
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/add-binary
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Ch03_AddBinary {
    /**
     * 方法1 ：都转换为 十进制，相加后，转为 二进制
     *
     * @param a
     * @param b
     * @return
     */
    public String addBinary1(String a, String b) {

        /*
        出现异常：
        java.lang.NumberFormatException: For input string: "10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101" under radix 2
          at line 67, java.base/java.lang.NumberFormatException.forInputString
          at line 711, java.base/java.lang.Long.parseLong
          at line 3, Solution.addBinary
          at line 54, __DriverSolution__.__helper__
          at line 87, __Driver__.main
         */
        long i = Long.parseLong(a, 2);
        long j = Long.parseLong(b, 2);
        String s = Long.toBinaryString(i + j);
        return s;


    }

    /**
     * 方法2：从最后一位逐层相加
     *
     * @param a 长度大的数组
     * @param b 长度小的数组
     * @return
     */
    public String addBinary2(String a, String b) {
        // 1. 定义变量
        int aIndex = a.length() - 1;
        int bIndex = b.length() - 1;
        // 2. 定义一个carry 决定，是否要进位
        int carry = 0;
        StringBuilder stringBuilder = new StringBuilder();

        while (aIndex > -1 || bIndex > -1){
            // 3. 定义sum ：求每一个位数上的相加的和
            int sum = carry;

            // 4. 遍历字符串 a
            if (aIndex > -1){
                // tips: 要减去 ‘0’ 的ASCII 码，就能转换为 int 的数字
                sum += a.charAt(aIndex --) - 48;
            }

            // 遍历字符串 b
            if (bIndex > -1){
                sum += b.charAt(bIndex --) - 48;
            }
            // 5. 获取结果判断是否要进位
            // 如果相加结果为2，carry 为 1，最后需要进位1
            // 如果相加结果为1或0，carry 为 0，则不需要进位
            carry = sum /2;

            // 6. 在数组中添加添加最后的结果
            // 如果相加为偶数，则加 0
            // 如果相加为1，则加1
            stringBuilder.append(sum % 2);
        }
        // 7. 判断最后是否要进位
        if (carry != 0){
            stringBuilder.append(carry);
        }

        // 8. 倒序输出结果
        return stringBuilder.reverse().toString();
    }

    public static void main(String[] args) {
        String s = new Ch03_AddBinary().addBinary2("1010", "1011");
        System.out.println(s);
    }

}
